Search Results

Documents authored by Thaler, Justin

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.22
Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches

Authors: Amit Chakrabarti, Prantar Ghosh, and Justin Thaler

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Abstract
We study graph computations in an enhanced data streaming setting, where a space-bounded client reading the edge stream of a massive graph may delegate some of its work to a cloud service. We seek algorithms that allow the client to verify a purported proof sent by the cloud service that the work done in the cloud is correct. A line of work starting with Chakrabarti et al. (ICALP 2009) has provided such algorithms, which we call schemes, for several statistical and graph-theoretic problems, many of which exhibit a tradeoff between the length of the proof and the space used by the streaming verifier. This work designs new schemes for a number of basic graph problems - including triangle counting, maximum matching, topological sorting, and single-source shortest paths - where past work had either failed to obtain smooth tradeoffs between these two key complexity measures or only obtained suboptimal tradeoffs. Our key innovation is having the verifier compute certain nonlinear sketches of the input stream, leading to either new or improved tradeoffs. In many cases, our schemes in fact provide optimal tradeoffs up to logarithmic factors. Specifically, for most graph problems that we study, it is known that the product of the verifier’s space cost v and the proof length h must be at least Ω(n²) for n-vertex graphs. However, matching upper bounds are only known for a handful of settings of h and v on the curve h ⋅ v = Θ̃(n²). For example, for counting triangles and maximum matching, schemes with costs lying on this curve are only known for (h = Õ(n²), v = Õ(1)), (h = Õ(n), v = Õ(n)), and the trivial (h = Õ(1), v = Õ(n²)). A major message of this work is that by exploiting nonlinear sketches, a significant "portion" of costs on the tradeoff curve h ⋅ v = n² can be achieved.
Cite as

Amit Chakrabarti, Prantar Ghosh, and Justin Thaler. Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 22:1-22:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chakrabarti_et_al:LIPIcs.APPROX/RANDOM.2020.22,
  author =	{Chakrabarti, Amit and Ghosh, Prantar and Thaler, Justin},
  title =	{{Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{22:1--22:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.22},
  URN =		{urn:nbn:de:0030-drops-126258},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.22},
  annote =	{Keywords: data streams, interactive proofs, Arthur-Merlin, graph algorithms}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.7
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials

Authors: Scott Aaronson, Robin Kothari, William Kretschmer, and Justin Thaler

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
We study quantum algorithms that are given access to trusted and untrusted quantum witnesses. We establish strong limitations of such algorithms, via new techniques based on Laurent polynomials (i.e., polynomials with positive and negative integer exponents). Specifically, we resolve the complexity of approximate counting, the problem of multiplicatively estimating the size of a nonempty set S ⊆ [N], in two natural generalizations of quantum query complexity. Our first result holds in the standard Quantum Merlin - Arthur (QMA) setting, in which a quantum algorithm receives an untrusted quantum witness. We show that, if the algorithm makes T quantum queries to S, and also receives an (untrusted) m-qubit quantum witness, then either m = Ω(|S|) or T = Ω(√{N/|S|}). This is optimal, matching the straightforward protocols where the witness is either empty, or specifies all the elements of S. As a corollary, this resolves the open problem of giving an oracle separation between SBP, the complexity class that captures approximate counting, and QMA. In our second result, we ask what if, in addition to a membership oracle for S, a quantum algorithm is also given "QSamples" - i.e., copies of the state |S⟩ = 1/√|S| ∑_{i ∈ S} |i⟩ - or even access to a unitary transformation that enables QSampling? We show that, even then, the algorithm needs either Θ(√{N/|S|}) queries or else Θ(min{|S|^{1/3},√{N/|S|}}) QSamples or accesses to the unitary. Our lower bounds in both settings make essential use of Laurent polynomials, but in different ways.
Cite as

Scott Aaronson, Robin Kothari, William Kretschmer, and Justin Thaler. Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 7:1-7:47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{aaronson_et_al:LIPIcs.CCC.2020.7,
  author =	{Aaronson, Scott and Kothari, Robin and Kretschmer, William and Thaler, Justin},
  title =	{{Quantum Lower Bounds for Approximate Counting via Laurent Polynomials}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{7:1--7:47},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.7},
  URN =		{urn:nbn:de:0030-drops-125593},
  doi =		{10.4230/LIPIcs.CCC.2020.7},
  annote =	{Keywords: Approximate counting, Laurent polynomials, QSampling, query complexity}
}
Document
DOI: 10.4230/LIPIcs.TQC.2020.2
Improved Approximate Degree Bounds for k-Distinctness

Authors: Nikhil S. Mande, Justin Thaler, and Shuchen Zhu

Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)

Abstract
An open problem that is widely regarded as one of the most important in quantum query complexity is to resolve the quantum query complexity of the k-distinctness function on inputs of size N. While the case of k=2 (also called Element Distinctness) is well-understood, there is a polynomial gap between the known upper and lower bounds for all constants k>2. Specifically, the best known upper bound is O (N^{(3/4)-1/(2^{k+2}-4)}) (Belovs, FOCS 2012), while the best known lower bound for k≥ 2 is Ω̃(N^{2/3} + N^{(3/4)-1/(2k)}) (Aaronson and Shi, J. ACM 2004; Bun, Kothari, and Thaler, STOC 2018). For any constant k ≥ 4, we improve the lower bound to Ω̃(N^{(3/4)-1/(4k)}). This yields, for example, the first proof that 4-distinctness is strictly harder than Element Distinctness. Our lower bound applies more generally to approximate degree. As a secondary result, we give a simple construction of an approximating polynomial of degree Õ(N^{3/4}) that applies whenever k ≤ polylog(N).
Cite as

Nikhil S. Mande, Justin Thaler, and Shuchen Zhu. Improved Approximate Degree Bounds for k-Distinctness. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 2:1-2:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{mande_et_al:LIPIcs.TQC.2020.2,
  author =	{Mande, Nikhil S. and Thaler, Justin and Zhu, Shuchen},
  title =	{{Improved Approximate Degree Bounds for k-Distinctness}},
  booktitle =	{15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)},
  pages =	{2:1--2:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-146-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{158},
  editor =	{Flammia, Steven T.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.2},
  URN =		{urn:nbn:de:0030-drops-120613},
  doi =		{10.4230/LIPIcs.TQC.2020.2},
  annote =	{Keywords: Quantum Query Complexity, Approximate Degree, Dual Polynomials, k-distinctness}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.40
Ad Hoc Multi-Input Functional Encryption

Authors: Shweta Agrawal, Michael Clear, Ophir Frieder, Sanjam Garg, Adam O'Neill, and Justin Thaler

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
Consider sources that supply sensitive data to an aggregator. Standard encryption only hides the data from eavesdroppers, but using specialized encryption one can hope to hide the data (to the extent possible) from the aggregator itself. For flexibility and security, we envision schemes that allow sources to supply encrypted data, such that at any point a dynamically-chosen subset of sources can allow an agreed-upon joint function of their data to be computed by the aggregator. A primitive called multi-input functional encryption (MIFE), due to Goldwasser et al. (EUROCRYPT 2014), comes close, but has two main limitations: - it requires trust in a third party, who is able to decrypt all the data, and - it requires function arity to be fixed at setup time and to be equal to the number of parties. To drop these limitations, we introduce a new notion of ad hoc MIFE. In our setting, each source generates its own public key and issues individual, function-specific secret keys to an aggregator. For successful decryption, an aggregator must obtain a separate key from each source whose ciphertext is being computed upon. The aggregator could obtain multiple such secret-keys from a user corresponding to functions of varying arity. For this primitive, we obtain the following results: - We show that standard MIFE for general functions can be bootstrapped to ad hoc MIFE for free, i.e. without making any additional assumption. - We provide a direct construction of ad hoc MIFE for the inner product functionality based on the Learning with Errors (LWE) assumption. This yields the first construction of this natural primitive based on a standard assumption. At a technical level, our results are obtained by combining standard MIFE schemes and two-round secure multiparty computation (MPC) protocols in novel ways highlighting an interesting interplay between MIFE and two-round MPC.
Cite as

Shweta Agrawal, Michael Clear, Ophir Frieder, Sanjam Garg, Adam O'Neill, and Justin Thaler. Ad Hoc Multi-Input Functional Encryption. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 40:1-40:41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.ITCS.2020.40,
  author =	{Agrawal, Shweta and Clear, Michael and Frieder, Ophir and Garg, Sanjam and O'Neill, Adam and Thaler, Justin},
  title =	{{Ad Hoc Multi-Input Functional Encryption}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{40:1--40:41},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.40},
  URN =		{urn:nbn:de:0030-drops-117258},
  doi =		{10.4230/LIPIcs.ITCS.2020.40},
  annote =	{Keywords: Multi-Input Functional Encryption}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.55
The Large-Error Approximate Degree of AC^0

Authors: Mark Bun and Justin Thaler

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
We prove two new results about the inability of low-degree polynomials to uniformly approximate constant-depth circuits, even to slightly-better-than-trivial error. First, we prove a tight Omega~(n^{1/2}) lower bound on the threshold degree of the SURJECTIVITY function on n variables. This matches the best known threshold degree bound for any AC^0 function, previously exhibited by a much more complicated circuit of larger depth (Sherstov, FOCS 2015). Our result also extends to a 2^{Omega~(n^{1/2})} lower bound on the sign-rank of an AC^0 function, improving on the previous best bound of 2^{Omega(n^{2/5})} (Bun and Thaler, ICALP 2016). Second, for any delta>0, we exhibit a function f : {-1,1}^n -> {-1,1} that is computed by a circuit of depth O(1/delta) and is hard to approximate by polynomials in the following sense: f cannot be uniformly approximated to error epsilon=1-2^{-Omega(n^{1-delta})}, even by polynomials of degree n^{1-delta}. Our recent prior work (Bun and Thaler, FOCS 2017) proved a similar lower bound, but which held only for error epsilon=1/3. Our result implies 2^{Omega(n^{1-delta})} lower bounds on the complexity of AC^0 under a variety of basic measures such as discrepancy, margin complexity, and threshold weight. This nearly matches the trivial upper bound of 2^{O(n)} that holds for every function. The previous best lower bound on AC^0 for these measures was 2^{Omega(n^{1/2})} (Sherstov, FOCS 2015). Additional applications in learning theory, communication complexity, and cryptography are described.
Cite as

Mark Bun and Justin Thaler. The Large-Error Approximate Degree of AC^0. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 55:1-55:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bun_et_al:LIPIcs.APPROX-RANDOM.2019.55,
  author =	{Bun, Mark and Thaler, Justin},
  title =	{{The Large-Error Approximate Degree of AC^0}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{55:1--55:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.55},
  URN =		{urn:nbn:de:0030-drops-112709},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.55},
  annote =	{Keywords: approximate degree, discrepancy, margin complexity, polynomial approximations, secret sharing, threshold circuits}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.71
Approximate Degree, Secret Sharing, and Concentration Phenomena

Authors: Andrej Bogdanov, Nikhil S. Mande, Justin Thaler, and Christopher Williamson

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
The epsilon-approximate degree deg~_epsilon(f) of a Boolean function f is the least degree of a real-valued polynomial that approximates f pointwise to within epsilon. A sound and complete certificate for approximate degree being at least k is a pair of probability distributions, also known as a dual polynomial, that are perfectly k-wise indistinguishable, but are distinguishable by f with advantage 1 - epsilon. Our contributions are: - We give a simple, explicit new construction of a dual polynomial for the AND function on n bits, certifying that its epsilon-approximate degree is Omega (sqrt{n log 1/epsilon}). This construction is the first to extend to the notion of weighted degree, and yields the first explicit certificate that the 1/3-approximate degree of any (possibly unbalanced) read-once DNF is Omega(sqrt{n}). It draws a novel connection between the approximate degree of AND and anti-concentration of the Binomial distribution. - We show that any pair of symmetric distributions on n-bit strings that are perfectly k-wise indistinguishable are also statistically K-wise indistinguishable with at most K^{3/2} * exp (-Omega (k^2/K)) error for all k < K <= n/64. This bound is essentially tight, and implies that any symmetric function f is a reconstruction function with constant advantage for a ramp secret sharing scheme that is secure against size-K coalitions with statistical error K^{3/2} * exp (-Omega (deg~_{1/3}(f)^2/K)) for all values of K up to n/64 simultaneously. Previous secret sharing schemes required that K be determined in advance, and only worked for f=AND. Our analysis draws another new connection between approximate degree and concentration phenomena. As a corollary of this result, we show that for any d <= n/64, any degree d polynomial approximating a symmetric function f to error 1/3 must have coefficients of l_1-norm at least K^{-3/2} * exp ({Omega (deg~_{1/3}(f)^2/d)}). We also show this bound is essentially tight for any d > deg~_{1/3}(f). These upper and lower bounds were also previously only known in the case f=AND.
Cite as

Andrej Bogdanov, Nikhil S. Mande, Justin Thaler, and Christopher Williamson. Approximate Degree, Secret Sharing, and Concentration Phenomena. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 71:1-71:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bogdanov_et_al:LIPIcs.APPROX-RANDOM.2019.71,
  author =	{Bogdanov, Andrej and Mande, Nikhil S. and Thaler, Justin and Williamson, Christopher},
  title =	{{Approximate Degree, Secret Sharing, and Concentration Phenomena}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{71:1--71:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.71},
  URN =		{urn:nbn:de:0030-drops-112869},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.71},
  annote =	{Keywords: approximate degree, dual polynomial, pseudorandomness, polynomial approximation, secret sharing}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.30
Sign-Rank Can Increase Under Intersection

Authors: Mark Bun, Nikhil S. Mande, and Justin Thaler

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
The communication class UPP^{cc} is a communication analog of the Turing Machine complexity class PP. It is characterized by a matrix-analytic complexity measure called sign-rank (also called dimension complexity), and is essentially the most powerful communication class against which we know how to prove lower bounds. For a communication problem f, let f wedge f denote the function that evaluates f on two disjoint inputs and outputs the AND of the results. We exhibit a communication problem f with UPP^{cc}(f)= O(log n), and UPP^{cc}(f wedge f) = Theta(log^2 n). This is the first result showing that UPP communication complexity can increase by more than a constant factor under intersection. We view this as a first step toward showing that UPP^{cc}, the class of problems with polylogarithmic-cost UPP communication protocols, is not closed under intersection. Our result shows that the function class consisting of intersections of two majorities on n bits has dimension complexity n^{Omega(log n)}. This matches an upper bound of (Klivans, O'Donnell, and Servedio, FOCS 2002), who used it to give a quasipolynomial time algorithm for PAC learning intersections of polylogarithmically many majorities. Hence, fundamentally new techniques will be needed to learn this class of functions in polynomial time.
Cite as

Mark Bun, Nikhil S. Mande, and Justin Thaler. Sign-Rank Can Increase Under Intersection. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bun_et_al:LIPIcs.ICALP.2019.30,
  author =	{Bun, Mark and Mande, Nikhil S. and Thaler, Justin},
  title =	{{Sign-Rank Can Increase Under Intersection}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{30:1--30:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.30},
  URN =		{urn:nbn:de:0030-drops-106067},
  doi =		{10.4230/LIPIcs.ICALP.2019.30},
  annote =	{Keywords: Sign rank, dimension complexity, communication complexity, learning theory}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.35
Approximate Degree and the Complexity of Depth Three Circuits

Authors: Mark Bun and Justin Thaler

Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)

Abstract
Threshold weight, margin complexity, and Majority-of-Threshold circuit size are basic complexity measures of Boolean functions that arise in learning theory, communication complexity, and circuit complexity. Each of these measures might exhibit a chasm at depth three: namely, all polynomial size Boolean circuits of depth two have polynomial complexity under the measure, but there may exist Boolean circuits of depth three that have essentially maximal complexity exp(Theta(n)). However, existing techniques are far from showing this: for all three measures, the best lower bound for depth three circuits is exp(Omega(n^{2/5})). Moreover, prior methods exclusively study block-composed functions. Such methods appear intrinsically unable to prove lower bounds better than exp(Omega(sqrt{n})) even for depth four circuits, and have yet to prove lower bounds better than exp(Omega(sqrt{n})) for circuits of any constant depth. We take a step toward showing that all of these complexity measures indeed exhibit a chasm at depth three. Specifically, for any arbitrarily small constant delta > 0, we exhibit a depth three circuit of polynomial size (in fact, an O(log n)-decision list) of complexity exp(Omega(n^{1/2-delta})) under each of these measures. Our methods go beyond the block-composed functions studied in prior work, and hence may not be subject to the same barriers. Accordingly, we suggest natural candidate functions that may exhibit stronger bounds.
Cite as

Mark Bun and Justin Thaler. Approximate Degree and the Complexity of Depth Three Circuits. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 35:1-35:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bun_et_al:LIPIcs.APPROX-RANDOM.2018.35,
  author =	{Bun, Mark and Thaler, Justin},
  title =	{{Approximate Degree and the Complexity of Depth Three Circuits}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{35:1--35:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.35},
  URN =		{urn:nbn:de:0030-drops-94390},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.35},
  annote =	{Keywords: approximate degree, communication complexity, learning theory, polynomial approximation, threshold circuits}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.17
Lower Bounds for the Approximate Degree of Block-Composed Functions

Authors: Justin Thaler

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We describe a new hardness amplification result for point-wise approximation of Boolean functions by low-degree polynomials. Specifically, for any function f on N bits, define F(x_1,...,x_M) = OMB(f(x_1),...,f(x_M)) to be the function on M*N bits obtained by block-composing f with a function known as ODD-MAX-BIT. We show that, if f requires large degree to approximate to error 2/3 in a certain one-sided sense (captured by a complexity measure known as positive one-sided approximate degree), then F requires large degree to approximate even to error 1-2^{-M}. This generalizes a result of Beigel (Computational Complexity, 1994), who proved an identical result for the special case f=OR. Unlike related prior work, our result implies strong approximate degree lower bounds even for many functions F that have low threshold degree. Our proof is constructive: we exhibit a solution to the dual of an appropriate linear program capturing the approximate degree of any function. We describe several applications, including improved separations between the complexity classes P^{NP} and PP in both the query and communication complexity settings. Our separations improve on work of Beigel (1994) and Buhrman, Vereshchagin, and de Wolf (CCC, 2007).
Cite as

Justin Thaler. Lower Bounds for the Approximate Degree of Block-Composed Functions. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{thaler:LIPIcs.ICALP.2016.17,
  author =	{Thaler, Justin},
  title =	{{Lower Bounds for the Approximate Degree of Block-Composed Functions}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.17},
  URN =		{urn:nbn:de:0030-drops-63133},
  doi =		{10.4230/LIPIcs.ICALP.2016.17},
  annote =	{Keywords: approximate degree, one-sided approximate degree, polynomial approx- imations, threshold degree, communication complexity}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.37
Improved Bounds on the Sign-Rank of AC^0

Authors: Mark Bun and Justin Thaler

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
The sign-rank of a matrix A with entries in {-1, +1} is the least rank of a real matrix B with A_{ij}*B_{ij} > 0 for all i, j. Razborov and Sherstov (2008) gave the first exponential lower bounds on the sign-rank of a function in AC^0, answering an old question of Babai, Frankl, and Simon (1986). Specifically, they exhibited a matrix A = [F(x,y)]_{x,y} for a specific function F:{-1,1}^n*{-1,1}^n -> {-1,1} in AC^0, such that A has sign-rank exp(Omega(n^{1/3}). We prove a generalization of Razborov and Sherstov’s result, yielding exponential sign-rank lower bounds for a non-trivial class of functions (that includes the function used by Razborov and Sherstov). As a corollary of our general result, we improve Razborov and Sherstov's lower bound on the sign-rank of AC^0 from exp(Omega(n^{1/3})) to exp(~Omega(n^{2/5})). We also describe several applications to communication complexity, learning theory, and circuit complexity.
Cite as

Mark Bun and Justin Thaler. Improved Bounds on the Sign-Rank of AC^0. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 37:1-37:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bun_et_al:LIPIcs.ICALP.2016.37,
  author =	{Bun, Mark and Thaler, Justin},
  title =	{{Improved Bounds on the Sign-Rank of AC^0}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{37:1--37:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.37},
  URN =		{urn:nbn:de:0030-drops-63173},
  doi =		{10.4230/LIPIcs.ICALP.2016.37},
  annote =	{Keywords: Sign-rank, circuit complexity, communication complexity, constant-depth circuits}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.59
Semi-Streaming Algorithms for Annotated Graph Streams

Authors: Justin Thaler

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
Considerable effort has been devoted to the development of streaming algorithms for analyzing massive graphs. Unfortunately, many results have been negative, establishing that a wide variety of problems require Omega(n^2) space to solve. One of the few bright spots has been the development of semi-streaming algorithms for a handful of graph problems - these algorithms use space O(n*polylog(n)). In the annotated data streaming model of Chakrabarti et al. [Chakrabarti/Cormode/Goyal/Thaler, ACM Trans. on Alg. 2014], a computationally limited client wants to compute some property of a massive input, but lacks the resources to store even a small fraction of the input, and hence cannot perform the desired computation locally. The client therefore accesses a powerful but untrusted service provider, who not only performs the requested computation, but also proves that the answer is correct. We consider the notion of semi-streaming algorithms for annotated graph streams (semistreaming annotation schemes for short). These are protocols in which both the client's space usage and the length of the proof are O(n*polylog(n)). We give evidence that semi-streaming annotation schemes represent a more robust solution concept than does the standard semi-streaming model. On the positive side, we give semi-streaming annotation schemes for two dynamic graph problems that are intractable in the standard model: (exactly) counting triangles, and (exactly) computing maximum matchings. The former scheme answers a question of Cormode [Cormode, Problem 47]. On the negative side, we identify for the first time two natural graph problems (connectivity and bipartiteness in a certain edge update model) that can be solved in the standard semi-streaming model, but cannot be solved by annotation schemes of "sub-semi-streaming" cost. That is, these problems are as hard in the annotations model as they are in the standard model.
Cite as

Justin Thaler. Semi-Streaming Algorithms for Annotated Graph Streams. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 59:1-59:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{thaler:LIPIcs.ICALP.2016.59,
  author =	{Thaler, Justin},
  title =	{{Semi-Streaming Algorithms for Annotated Graph Streams}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{59:1--59:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.59},
  URN =		{urn:nbn:de:0030-drops-62247},
  doi =		{10.4230/LIPIcs.ICALP.2016.59},
  annote =	{Keywords: graph streams, stream verification, annotated data streams, probabilistic proof systems}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2016.6
A Framework for Estimating Stream Expression Cardinalities

Authors: Anirban Dasgupta, Kevin J. Lang, Lee Rhodes, and Justin Thaler

Published in: LIPIcs, Volume 48, 19th International Conference on Database Theory (ICDT 2016)

Abstract
Given m distributed data streams A_1,..., A_m, we consider the problem of estimating the number of unique identifiers in streams defined by set expressions over A_1,..., A_m. We identify a broad class of algorithms for solving this problem, and show that the estimators output by any algorithm in this class are perfectly unbiased and satisfy strong variance bounds. Our analysis unifies and generalizes a variety of earlier results in the literature. To demonstrate its generality, we describe several novel sampling algorithms in our class, and show that they achieve a novel tradeoff between accuracy, space usage, update speed, and applicability.
Cite as

Anirban Dasgupta, Kevin J. Lang, Lee Rhodes, and Justin Thaler. A Framework for Estimating Stream Expression Cardinalities. In 19th International Conference on Database Theory (ICDT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 48, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{dasgupta_et_al:LIPIcs.ICDT.2016.6,
  author =	{Dasgupta, Anirban and Lang, Kevin J. and Rhodes, Lee and Thaler, Justin},
  title =	{{A Framework for Estimating Stream Expression Cardinalities}},
  booktitle =	{19th International Conference on Database Theory (ICDT 2016)},
  pages =	{6:1--6:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-002-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{48},
  editor =	{Martens, Wim and Zeume, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2016.6},
  URN =		{urn:nbn:de:0030-drops-57754},
  doi =		{10.4230/LIPIcs.ICDT.2016.6},
  annote =	{Keywords: sketching, data stream algorithms, mergeability, distinct elements, set operations}
}
Document
DOI: 10.4230/LIPIcs.CCC.2015.217
Verifiable Stream Computation and Arthur–Merlin Communication

Authors: Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, and Suresh Venkatasubramanian

Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)

Abstract
In the setting of streaming interactive proofs (SIPs), a client (verifier) needs to compute a given function on a massive stream of data, arriving online, but is unable to store even a small fraction of the data. It outsources the processing to a third party service (prover), but is unwilling to blindly trust answers returned by this service. Thus, the service cannot simply supply the desired answer; it must convince the verifier of its correctness via a short interaction after the stream has been seen. In this work we study "barely interactive" SIPs. Specifically, we show that two or three rounds of interaction suffice to solve several query problems - including Index, Median, Nearest Neighbor Search, Pattern Matching, and Range Counting - with polylogarithmic space and communication costs. Such efficiency with O(1) rounds of interaction was thought to be impossible based on previous work. On the other hand, we initiate a formal study of the limitations of constant-round SIPs by introducing a new hierarchy of communication models called Online Interactive Proofs (OIPs). The online nature of these models is analogous to the streaming restriction placed upon the verifier in an SIP. We give upper and lower bounds that (1) characterize, up to quadratic blowups, every finite level of the OIP hierarchy in terms of other well-known communication complexity classes, (2) separate the first four levels of the hierarchy, and (3) reveal that the hierarchy collapses to the fourth level. Our study of OIPs reveals marked contrasts and some parallels with the classic Turing Machine theory of interactive proofs, establishes limits on the power of existing techniques for developing constant-round SIPs, and provides a new characterization of (non-online) Arthur-Merlin communication in terms of an online model.
Cite as

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, and Suresh Venkatasubramanian. Verifiable Stream Computation and Arthur–Merlin Communication. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 217-243, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{chakrabarti_et_al:LIPIcs.CCC.2015.217,
  author =	{Chakrabarti, Amit and Cormode, Graham and McGregor, Andrew and Thaler, Justin and Venkatasubramanian, Suresh},
  title =	{{Verifiable Stream Computation and Arthur–Merlin Communication}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{217--243},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{Zuckerman, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.217},
  URN =		{urn:nbn:de:0030-drops-50680},
  doi =		{10.4230/LIPIcs.CCC.2015.217},
  annote =	{Keywords: Arthur-Merlin communication complexity, streaming interactive proofs}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact